백준 11723번

오늘 풀어본 문제는 백준의 11723번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 3

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

add $x$: $S$에 $x$를 추가한다. $(1 \leq x \leq 20)$
$S$에 $x$가 이미 있는 경우에는 연산을 무시한다.
remove $x$: $S$에서 $x$를 제거한다. $(1 \leq x \leq 20)$
$S$에 $x$가 없는 경우에는 연산을 무시한다.
check $x$: $S$에 $x$가 있으면 $1$을, 없으면 $0$을 출력한다. $(1 \leq x \leq 20)$
toggle $x$: $S$에 $x$가 있으면 $x$를 제거하고, 없으면 $x$를 추가한다. $(1 \leq x \leq 20)$
all: $S$를 ${1, 2, \cdots, 20}$ 으로 바꾼다.
empty: $S$를 공집합으로 바꾼다.

입력

첫째 줄에 수행해야 하는 연산의 수 $M$ $(1 \leq M \leq 3,000,000)$이 주어진다.

둘째 줄부터 $M$개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

출력

check 연산이 주어질때마다, 결과를 출력한다.

풀이과정

첫 번째 시도

나는 C++ 언어를 PS용 주력 언어로 사용하기 때문에 이런 종류의 문제를 풀 때 사용할 수 있는 STL이 있는지를 보통 먼저 찾아본다.

집합이라는 이름을 가지고 있길래, 관련해서 검색을 해보니 std::set 이라는 STL이 있었다. 이 글²을 참고하여 std::set 의 기능을 활용하여 코드를 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

int main(void) {

	ios::sync_with_stdio(0);
	cin.tie(0);

	int numberOfCommands, element;
	string tempCommand;

	set<int> S;
	
	cin >> numberOfCommands;

	while (numberOfCommands--) {
		cin >> tempCommand;

		if (tempCommand == "add") {
			cin >> element;
			S.insert(element);
		}
		else if (tempCommand == "remove") {
			cin >> element;
			S.erase(element);
		}
		else if (tempCommand == "check") {
			cin >> element;
			cout << S.count(element) << "\n";
		}
		else if (tempCommand == "toggle") {
			if (S.count(element)) {
				S.erase(element);
			}
			else {
				S.insert(element);
			}
		}
		else if (tempCommand == "all") {
			S.clear();
			for (int i = 1; i <= 20; i++) {
				S.insert(i);
			}
		}
		else if (tempCommand == "empty") {
			S.clear();
		}
	}

	return 0;
}

결과는 시간 초과가 발생했고, std::set 을 이용해서는 시간 초과가 발생하기 때문에 다른 방식을 택해야 했다.

두 번째 시도

문제의 알고리즘 분류를 살펴보니, 비트마스킹이 있었다. 비트마스킹은 어떤 정보를 각 비트에 저장하고 비트 연산자를 이용하여 그 정보들을 변경하는 방식이다.

이 집합 문제에서는 어떤 원소가 존재하거나 존재하지 않는 2가지 경우만 있기 때문에 이러한 비트 마스킹을 활용할 수 있다는 것을 깨닫게 되었다.

그리고 $x$의 범위가 1에서 20사이라는 점을 이용하여 변수의 각 비트에 해당 정보를 저장하는 방식으로 코드를 짜보게 되었다.

#include <bits/stdc++.h>

using namespace std;

int main(void) {

	ios::sync_with_stdio(0);
	cin.tie(0);

	int numberOfCommands, element;
	string tempCommand;

	unsigned int S;
	
	cin >> numberOfCommands;

	while (numberOfCommands--) {
		cin >> tempCommand;

		if (tempCommand == "add") {
			cin >> element;
			S |= (1 << element);
		}
		else if (tempCommand == "remove") {
			cin >> element;
			S &= ~(1 << element);
		}
		else if (tempCommand == "check") {
			cin >> element;
			if (S & (1 << element)) {
				cout << "1\n";
			}
			else {
				cout << "0\n";
			}
		}
		else if (tempCommand == "toggle") {
			cin >> element;
			S ^= (1 << element);
		}
		else if (tempCommand == "all") {
			S = (1 << 21) - 1;
		}
		else if (tempCommand == "empty") {
			S = 0;
		}
	}

	return 0;
}

시간 초과 문제는 해결이 되었으나, 예상과 달리 오답이었다.

세 번째 시도

코드를 이리저리 살펴본 결과, 치명적인 실수를 하나 했음을 발견하게 되었다. 비트 정보들을 저장하는 변수 S가 초기화가 되지 않은 상태에서 사용되었기 때문에 예상치 못한 동작을 일으켜 오답이 발생하는 테스트 케이스가 있던 것이다. 그 부분을 코드를 수정하여 다음과 같이 제출하였다.

#include <bits/stdc++.h>

using namespace std;

int main(void) {

	ios::sync_with_stdio(0);
	cin.tie(0);

	int numberOfCommands, element;
	string tempCommand;

	unsigned int S = 0;
	
	cin >> numberOfCommands;

	while (numberOfCommands--) {
		cin >> tempCommand;

		if (tempCommand == "add") {
			cin >> element;
			S |= (1 << element);
		}
		else if (tempCommand == "remove") {
			cin >> element;
			S &= ~(1 << element);
		}
		else if (tempCommand == "check") {
			cin >> element;
			if (S & (1 << element)) {
				cout << "1\n";
			}
			else {
				cout << "0\n";
			}
		}
		else if (tempCommand == "toggle") {
			cin >> element;
			S ^= (1 << element);
		}
		else if (tempCommand == "all") {
			S = (1 << 21) - 1;
		}
		else if (tempCommand == "empty") {
			S = 0;
		}
	}

	return 0;
}

그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.

마무리

이번 문제는 앞에서도 이야기 한 것처럼 비트마스킹을 활용하는 것이 핵심인 문제였다. 비트마스킹에 대해서 모르는 것은 아니지만, 오랫동안 써본 적이 없어 바로 떠올리지 못한 점이 아쉬웠다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/11723
2: https://0-sunny.tistory.com/65

← Previous Post Next Post →